/**
 * @file 086.分割回文子字符串.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-19
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    vector<vector<string>> partition(string s)
    {
        backtracking(s, 0);
        return res;
    }

private:
    vector<vector<string>> res;
    vector<string> path;
    bool isPalindrome(string &s, int i, int j)
    {
        while (i < j) {
            if (s[i++] != s[j--]) {
                return false;
            }
        }
        return true;
    }
    void backtracking(string &s, int startIdx)
    {
        if (startIdx == s.length()) {
            res.emplace_back(path);
            return;
        }
        for (int i = startIdx; i < s.length(); ++i) {
            if (!isPalindrome(s, startIdx, i)) {
                continue;
            }
            path.push_back(string(s.substr(startIdx, i - startIdx + 1)));
            backtracking(s, i + 1);
            path.pop_back();
        }
    }
};

template <class T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main()
{
    auto res = Solution().partition("google");
    for (auto &r : res) {
        print(r);
    }
    cout << endl;
    res = Solution().partition("aab");
    for (auto &r : res) {
        print(r);
    }
    cout << endl;
    res = Solution().partition("a");
    for (auto &r : res) {
        print(r);
    }
    return 0;
}